package com.lft.sort03.insertion_sort;

import java.util.Arrays;

public class InsertionSort {
	public static void main(String[] args) {
		int[] a = {101, 34, 119, 1};
		System.out.println(Arrays.toString(insertionSort(a)));
	}
	
	public static int[] insertionSort(int[] a) {
		// 插入排序的时间复杂度：平均：O(n^2)，最差：O(n^2)
		int insertVal;
		int insertIndex;
		for (int i = 1; i < a.length; i++) {
			insertVal = a[i];
			insertIndex = i - 1;
			while (insertIndex >= 0 && insertVal < a[insertIndex]) {
				a[insertIndex + 1] = a[insertIndex];
				insertIndex--;
			}
			// if (insertIndex + 1 == i) { // 不需要加判断，会增加耗时和内存。
			a[insertIndex + 1] = insertVal;
			// }
		}
		return a;
		
		// // 使用逐步推导
		// // 第 1 轮 {101, 34, 119, 1} =》{34, 101, 119, 1}
		// // 定义待插入的数
		// int insertVal = a[1];
		// // 待插入的数前面一个数的下标。
		// int insertIndex = 1 - 1;
		// // 给 insertVal 找到插入的位置
		// // 说明：
		// // 1. insertIndex >= 0 保证在给 insertVal 找插入位置时，下标不越界。
		// // 2. insertVal < a[insertIndex] 待插入的数，还没有找到插入位置
		// // 3. 就需要将 a[insertIndex] 后移
		// while (insertIndex >= 0 && insertVal < a[insertIndex]) {
		// 	a[insertIndex + 1] = a[insertIndex];
		// 	insertIndex--;
		// }
		// // 当退出 while 循环时，说明插入的位置找到，insertIndex + 1
		// a[insertIndex + 1] = insertVal;
		//
		// // 第 2 轮 {34, 101, 119, 1} =》{34, 101, 119, 1}
		// // 定义待插入的数
		// insertVal = a[2];
		// // 待插入的数前面一个数的下标。
		// insertIndex = 2 - 1;
		// // 给 insertVal 找到插入的位置
		// // 说明：
		// // 1. insertIndex >= 0 保证在给 insertVal 找插入位置时，下标不越界。
		// // 2. insertVal < a[insertIndex] 待插入的数，还没有找到插入位置
		// // 3. 就需要将 a[insertIndex] 后移
		// while (insertIndex >= 0 && insertVal < a[insertIndex]) {
		// 	a[insertIndex + 1] = a[insertIndex];
		// 	insertIndex--;
		// }
		// // 当退出 while 循环时，说明插入的位置找到，insertIndex + 1
		// a[insertIndex + 1] = insertVal;
		//
		// // 第 3 轮 {34, 101, 119, 1} =》{1, 34, 101, 119}
		// // 定义待插入的数
		// insertVal = a[3];
		// // 待插入的数前面一个数的下标。
		// insertIndex = 3 - 1;
		// // 给 insertVal 找到插入的位置
		// // 说明：
		// // 1. insertIndex >= 0 保证在给 insertVal 找插入位置时，下标不越界。
		// // 2. insertVal < a[insertIndex] 待插入的数，还没有找到插入位置
		// // 3. 就需要将 a[insertIndex] 后移
		// while (insertIndex >= 0 && insertVal < a[insertIndex]) {
		// 	a[insertIndex + 1] = a[insertIndex];
		// 	insertIndex--;
		// }
		// // 当退出 while 循环时，说明插入的位置找到，insertIndex + 1
		// a[insertIndex + 1] = insertVal;
		// return a;
	}
}
